문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
접근
연구실에서 바이러스가 퍼진 부분을 찾아야하니 그래프를 이용하는 문제입니다.
하지만 벽 세 개는 어떻게 해야할지…
저는 처음에 입력 받은 그래프에서 2인 부분을 중심으로 벽을 설치하는 방법을 생각했는데 전혀 규칙이 없어서 두세시간 쯤 고민하고 구글링을 해보았습니다.
실제로 이렇게 열심히 규칙을 찾아보았습니다…
결론적으로 방법은 브루트포스 알고리즘과 BFS를 모두 사용해야 합니다.
즉, 벽 세 개 설치에 규칙은 없고 전체의 경우를 다 확인해야 하는 것입니다. 실제로 문제의 시간 제한은 2초로 전에 풀었던 문제의 두 배이네요.
저는 Solution 클래스와 Position 클래스를 만들었습니다.
- Solution 클래스: 입력된 데이터를 저장하며, 주어진 문제를 풀기 위한 메소드를 가지고 있습니다.
- Position 클래스: x, y 위치를 저장
- max: 최대 안전 영역을 저장하는 필드로, makeWall 메소드가 끝나면 최종적으로 최대 값이 저장됩니다.
- Solution(생성자): 입력받은 데이터 전달 받습니다.
- makeWall(): 재귀를 이용해 벽을 세웁니다. count가 3이 되면 BFS 메소드로 안전 영역 크기를 반환합니다.
- BFS(): 저장되어 있는 그래프 데이터를 BFS로 돌며 바이러스를 전달하고, 남은 안전 영역 크기를 저장합니다.
Solution(int N, int M, int[][] lab)
makeWall()
재귀를 통해 벽을 세우는 모든 경우의 수를 탐색합니다.
세워진 벽의 수가 3개가 되면 BFS를 수행해서 안전 영역 크기를 구합니다.
BFS()
우선 원래 입력 값을 보존하기 위해 배열을 복사 합니다.
그 후, 바이러스가 있는 부분의 좌표를 큐에 저장합니다.
큐를 돌며 바이러스를 상하좌우로 퍼뜨리고, 퍼뜨려진 부분을 다시 큐에 넣고를 반복합니다.
기초적인 로직은 BFS 알고리즘입니다.
이렇게 하면 끝!
참고로 main 부분 첨부합니다.
main
결과
사용 연어: Java 11
| 메모리 | 시간 |
| 297636 KB | 872 ms |
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.